package cn.secby.wms.util;

import lombok.Data;

import java.util.*;

@Data
public class TabuSearch {
    public  final int MAX_GEN = 300;//最大的迭代次数(提高这个值可以稳定地提高解质量，但是会增加求解时间)
    public  final int N = 50;//每次搜索领域的个数(这个值不要太大，太大的话搜索效率会降低)
    public  int sqNum ;//矩形数量，手动设置
    public HashMap<String,TabuMapTree> tabuTreeMap = new HashMap<>();
    public  List<Square> initGhh;//初始顺序
    public  List<Square> bestGh;//最佳顺序
    public  List<Square> LocalGh;//当前最好顺序
    public List<Square> tempGh;//存放临时顺序
    public  int bestT;//最佳的迭代次数
    public Solution bestSolution;//最优解
    public  Solution LocalSolution;//每次领域搜索的最优解（领域最优解）
    public  Solution tempSolution;//临时解
    public  int t;//当前迭代
    public Random random;//随机函数对象
    // 问题实例
    public Instance instance;
    double L,W;

    public TabuSearch(Instance instance) throws Exception {
        this.instance = instance;
        this.initGhh = new ArrayList<>(instance.getSquareList());
        // 初始化变量
        random = new Random(System.currentTimeMillis());
        L = instance.getL();
        W = instance.getW();
        sqNum = initGhh.size();
    }
    public Solution search() throws Exception {
        // 获取初始解
        getInitSolution();
        System.out.println(bestSolution.getRate());
        //开始迭代，停止条件为达到指定迭代次数
        while (t<=MAX_GEN){
            //当前领域搜索次数
            int n = 0;
            LocalSolution = new Solution();
            LocalSolution.setRate(0);
            while (n <= N){
                // 随机打乱顺序 得到当前编码Ghh的邻居编码tempGh
                tempGh = generateNewGh(new ArrayList<>(initGhh),new ArrayList<>(tempGh));
                // 判断其是否在禁忌表中
                if(!judge(tempGh)){
                    // 如果不在
                    // 加入禁忌表
                    enterTabooList(tempGh);
                    tempSolution = evaluate(tempGh);
                    if(tempSolution.getRate() > LocalSolution.getRate()){
                        // 如果临时解优于本次领域搜索的最优解
                        // 那么就将临时解替换本次领域搜索的最优解
                        LocalGh = new ArrayList<>(tempGh);
                        LocalSolution = tempSolution;
                    }
                }else{
                    throw new Exception("重复");
                }
                n++;
            }
            if(LocalSolution.getRate() > bestSolution.getRate()){
                //如果本次搜索的最优解优于全局最优解
                //那么领域最优解替换全局最优解
                bestT = t;
                bestGh = new ArrayList<>(LocalGh);
                bestSolution = LocalSolution;
//                bestSolution = evaluate(bestGh);
            }
            initGhh = new ArrayList<>(LocalGh);
            t++;
            System.out.println("当前迭代次数为："+t+",当前最佳利用率为："+bestSolution.getRate());
        }
        //求解完毕
        System.out.println("最佳迭代次数:"+bestT);
        System.out.println("最佳利用率为:"+bestSolution.getRate());
        return bestSolution;
    }
    //评价函数
    public Solution evaluate(List<Square> squareList){
        Solution solution = new Solution();
        solution.setInstance(instance);
        solution.setSquareList(new ArrayList<>(squareList));
        List<PlaceSquare> placeSquareList = new ArrayList<>();
        // 创建可放置角点
        List<PlacePoint> placePointList = new ArrayList<>();
        placePointList.add(new PlacePoint(0,0));
        // 开始按照顺序和规则放置
        for (int i = 0; i < squareList.size(); i++) {
            PlacePoint placePoint = null;
            boolean b = false;
            Square square = squareList.get(i);
            for (int j = 0; j < placePointList.size(); j++) {
                placePoint = placePointList.get(j);
                PlaceSquare placeSquare = new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getL(),square.getW());
                if(!isOverlap(placeSquareList,placeSquare)){
                    b = true;
                    // 移除当前角点
                    placePointList.remove(j);
                    //新增已放置的square
                    placeSquareList.add(new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getL(),square.getW()));
                    // 新增两个可行角点
                    placePointList.add(new PlacePoint(placePoint.getX()+square.getL(),placePoint.getY()));
                    placePointList.add(new PlacePoint(placePoint.getX(),placePoint.getY()+square.getW()));
                    // 重新排序
                    Collections.sort(placePointList);
                    // 跳出内层循环
                    j = placePointList.size();
                }
            }
            if(!b && instance.isRotateEnable()){
                double l = square.getL();
                double w = square.getW();
                square.setL(w);
                square.setW(l);
                for (int j = 0; j < placePointList.size(); j++) {
                    placePoint = placePointList.get(j);
                    PlaceSquare placeSquare = new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getL(),square.getW());
                    if(!isOverlap(placeSquareList,placeSquare)){
                        b = true;
                        // 移除当前角点
                        placePointList.remove(j);
                        //新增已放置的square
                        placeSquareList.add(new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getL(),square.getW()));
                        // 新增两个可行角点
                        placePointList.add(new PlacePoint(placePoint.getX()+square.getL(),placePoint.getY()));
                        placePointList.add(new PlacePoint(placePoint.getX(),placePoint.getY()+square.getW()));
                        // 重新排序
                        Collections.sort(placePointList);
                        // 跳出内层循环
                        j = placePointList.size();
                    }
                }
                square.setL(l);
                square.setW(w);
            }
        }
        // 设置已经放置的矩形列表
        solution.setPlaceSquareList(new ArrayList<>(placeSquareList));
        // 计算利用率
        double rate = 0.0f;
        double s = 0.0f;
        for (PlaceSquare placeSquare : placeSquareList) {
            s += (placeSquare.getL()*placeSquare.getW());
        }
        rate = s/(L*W);
        solution.setRate(rate);
        return solution;
    }
    // 判断放置在该位置是否超出边界或者和其他矩形重叠
    public boolean isOverlap(List<PlaceSquare> placeSquareList,PlaceSquare tempPlaceSquare){
        // 出界
        if(tempPlaceSquare.getL()>L||tempPlaceSquare.getW()>W){
            return true;
        }
        // 出界
        if(tempPlaceSquare.getX()+tempPlaceSquare.getL()>L||tempPlaceSquare.getY()+tempPlaceSquare.getW()>W){
            return true;
        }
        for (PlaceSquare placeSquare : placeSquareList) {
            // 角点重合
            if(placeSquare.getX()==tempPlaceSquare.getX()&&placeSquare.getY()==tempPlaceSquare.getY()){
//                placeSquareList.remove(placeSquare);
//                return true;
            }
            // 判断即将要放置的块是否与之前放置的块有重叠
            if(isOverlap2(placeSquare,tempPlaceSquare)){
                return true;
            }
        }
        return false;
    }
    // 判断即将要放置的块是否与之前放置的块有重叠
    public boolean isOverlap2(PlaceSquare placeSquare,PlaceSquare tempPlaceSquare){

        double x1 = Math.max(placeSquare.getX(), tempPlaceSquare.getX());
        double y1 = Math.max(placeSquare.getY(), tempPlaceSquare.getY());
        double x2 = Math.min(placeSquare.getX()+placeSquare.getL(), tempPlaceSquare.getX()+tempPlaceSquare.getL());
        double y2 = Math.min(placeSquare.getY()+placeSquare.getW(), tempPlaceSquare.getY()+tempPlaceSquare.getW());

        if(x1 >= x2 || y1 >= y2) {
            return false;
        }

        return true;

    }
    // 生成初始解
    public void getInitSolution() throws Exception {
        bestSolution = evaluate(new ArrayList<>(initGhh));
        tempSolution = bestSolution;
        bestGh = new ArrayList<>(initGhh);
        tempGh = new ArrayList<>(initGhh);
        LocalGh = new ArrayList<>(initGhh);
    }
    //加入禁忌队列
    public void enterTabooList(List<Square> squareList){
        if(tabuTreeMap == null){
            tabuTreeMap = new HashMap<>();
        }
        Square square = squareList.get(0);
        String id = square.getId();
        if(tabuTreeMap.containsKey(id)){
            tabuTreeMap.get(id).add(new ArrayList<>(squareList),1);
        }else{
            TabuMapTree tabuMapTree = new TabuMapTree();
            tabuMapTree.setNodeSquare(square);
            tabuMapTree.add(new ArrayList<>(squareList),1);
            tabuTreeMap.put(id,tabuMapTree);
        }

    }
    //生成新解
    public List<Square> generateNewGh(List<Square> localGh,List<Square> tempGh) {
        tempGh = new ArrayList<>(localGh);
        Collections.shuffle(tempGh);
        return tempGh;
    }
    //判断路径编码是否存在于禁忌表中
    public boolean judge(List<Square> Gh){
        Square square = Gh.get(0);
        if(tabuTreeMap.containsKey(square.getId())){
            return tabuTreeMap.get(square.getId()).contains(Gh,1);
        }else{
            return false;
        }
    }
    // 判断两个Squre是否相等
    public boolean isEq(Square square1,Square square2){
        return square1.getId().equals(square2.getId());
    }
}
